\documentclass{ctexart}
\usepackage{float}%解决图片乱跑问题
\usepackage{geometry}%设置页面大小边距等
\usepackage{authblk}%作者机构等信息
\usepackage{graphicx}%插入图片
\usepackage{amssymb}%为了用\mathbb
\usepackage{amsmath}%数学方程的显示
\usepackage{listings}%插入代码
\usepackage{fancyhdr}%设置页眉页脚
\usepackage{lastpage}%总页数
\usepackage{tikz}
\usepackage{listings}%插入代码
\usepackage{hyperref}%引用网页
\usepackage{xcolor}%实现代码颜色高亮
\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}%一定要放在前面！
\lstset{frame=single,basicstyle=\ttfamily,columns=flexible,language={C},
keywordstyle=\bf\color{blue},
commentstyle=\it\color[RGB]{0,96,96},
numberstyle=\color[RGB]{0,192,192}}


\pagestyle{fancy}%设置页眉页脚
\lhead{陈冠宇\ 3200102033}%页眉左
\chead{Numerical Analysis}%页眉中
\rhead{HW4}%章节信息
\cfoot{\thepage/\pageref{LastPage}}%当前页，记得调用前文提到的宏包
\rfoot{School of Mathematical Sciences in ZJU}
\renewcommand{\headrulewidth}{0.1mm}%页眉线宽，设为0可以去页眉线
\renewcommand{\footrulewidth}{0.1mm}%页脚线宽，设为0可以去页眉线
\setlength{\headwidth}{\textwidth}

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}
\newtheorem{solution}{Solution:}
\newtheorem{remark}{Remark}

\hypersetup{%设置网页链接颜色等
    colorlinks=true,%链接将会有颜色，默认是红色
    urlcolor=blue,%链接到网站的链接将会变为蓝绿色（cyan）
    }

\title{Theoretical questions of Chapter3}
\everymath{\displaystyle}
\begin{document}
\section*{Theoretical questions of Chapter3}
\subsection*{\uppercase\expandafter{\romannumeral1}}
\begin{proof}
  To prove s(x) is a nature cubic spline, then we have to prove that $s''(a)=s''(b)=0.$

  Consider knots $x_1 = 0, x_2 = 1, x_3 = 2$, then $M_i,i\in\{1,2,3\}$ satisfy
  $$\mu _2M_1+2M_2+\lambda _2 M_3 = 6f[x_1,x_2,x_3].$$
  where $\mu _2 = \lambda _2 = \frac{1}{2}, M_2 = -3, M_3 = 0$.
  And $$\begin{aligned}f[x_1,x_2,x_3] &= \frac{f[x_2,x_3]-f[x_1,x_2]}{x_3-x_1}\\
  &=\frac{1}{2}(\frac{f[x_3]-f[x_2]}{x_3-x_2}-\frac{f[x_2]-f[x_1]}{x_2-x_1})\\
  &=\frac{1}{2}(-1-1)\\
  &=-1
  \end{aligned}$$

  Then $M_1 = s''(a) = M_3 =s''(b)=0 $

\subsection*{\uppercase\expandafter{\romannumeral2}}
(a)To determine s uniquely, we need at least three equations cause $s\in \mathbb{S}^2_3$

(b)Denote $K_{i}=f\left[x_{i}, x_{i+1}\right]$ . The table of divided difference for the Hermite interpolation problem is
$$\begin{array}{ccccc}
    x_{i}  & | & f_{i} &   &  \\
    x_{i} & | & f_{i} & m_{i} &   \\
    x_{i+1} & | & f_{i+1} & K_{i} & \frac{K_{i}-m_{i}}{x_{i+1}-x_{i}}
  \end{array}$$


Then the Newton formula yields

$$\begin{aligned}
p_{i}(x)=& f_{i}+\left(x-x_{i}\right) m_{i}+\left(x-x_{i}\right)^{2} \frac{K_{i}-m_{i}}{x_{i+1}-x_{i}}
\end{aligned}$$
(c)By (b), if we have $m_1$, then $m_2=p'_1(x_2)$.

Similarly if we have $m_i$, then we can compute $p_i(x)$, then we have $m_{i+1}=p'_i(x)$.

That is $m_2,m_3,\cdots, m_{n-1}$ can be computed.
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral3}}
\begin{proof}
  (a)Since we have $s(-1) = 1, s(0) = 1+c, s'_1(x)=3c(x+1)^2, s''_1(x)=6c(x+1)$, then $s'_1(-1)=0, s'_1(0)=3c,s''(0)=6c$

  To be a natural cubic spline, then $s''(-1)=s''(1)=0$

  Assume $s_2(x)=ax^3+bx^2+dx+e$, then $$\left\{
  \begin{aligned}
  &e =1+c\\
  &d=3c\\
  &2b = 6c\\
  &6a+2b =0
  \end{aligned}\right.$$
  Then $s_2(x)=-cx^3+3cx^2+3cx+1+c$

  (b)If $s(1) = -1$, then $-c+3c+3c+1+c = -1$. That is $c = -\frac{1}{3}$
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral4}}
\begin{solution}
  (a) Since $f = cos(\frac{\pi}{2}x)$ and f is cubic spline,
  Then we have
  $$\left\{
  \begin{aligned}
  f(-1)&=\cos(-\frac{\pi}{2})=0\\
  f(0) &= \cos(0) = 1\\
  f(1) &=\cos(\frac{\pi}{2}) = 0\\
  f''(-1) &= f''(1) = 0
  \end{aligned}
  \right.$$

  By lemma 3.6, we have $\mu_2M_1+2M_2+\lambda_2M_3=6f[x_1,x_2,x_3]$, where $\mu_i=(x_i-x_{i-1})/(x_{i+1}-x_{i-1}), \lambda_i = (x_{i+1}-x_i)/(x_{i+1}-x_{i-1})$ and $M_i = f''(x_i)$

  Hence $M_2 = -3$.

  Since $s'''(x_i)=(M_{i+1}-M_i)/(x_{i+1}-x_i)$, then $s'''(x_2) = 3$.

  Therefore $$\begin{aligned}
  s(x_2) &= f[x_2] + f[x_2,x_2](x-x_2) + \frac{M_2}{2}(x-x_2)^2+\frac{s'''(x_2)}{3!}(x-x_2)^3\\
  &= 1-\frac{3}{2}x^2+\frac{1}{2}x^3
  \end{aligned}$$

 Similarly $s'''(x_i)=(M_{i-1}-M_i)/(x_{i-1}-x_i)$, then $s'''(x_2) = -3$.

 Therefore, $s(x) = 1-\frac{3}{2}x^2-\frac{1}{2}x^3$

 That is $$s(x)=\left\{
 \begin{aligned}
 &1-\frac{3}{2}x^2-\frac{1}{2}x^3 \qquad x\in [-1,0]\\
 &1-\frac{3}{2}x^2+\frac{1}{2}x^3 \qquad x\in [0,1]
 \end{aligned}
 \right.$$
  (b)(i)Suppose $s(x)$ be the natural cubic spline, then we have $s''(f,-1) = 0$ and $s''(f,1)=0$.

  Since we have $$\left\{
  \begin{aligned}
  s(-1) &= f(-1) = 0\\
  s(0) &= f(0) = 1\\
  s(1) &= f(1) = 0
  \end{aligned}
  \right.$$

  Hence by (a), $$
  s''(x)=\left\{
  \begin{aligned}
  &-3x-3 \qquad x\in[-1,0]\\
  &3x-3 \qquad x\in [0,1]
  \end{aligned}
  \right.
  $$

  Hence $\int_{-1}{1}(s''(x))^2dx=6$
  (i)Since g(x) is quadratic polynomial interpolating f at -1, 0, 1, hence $g(x)=1-x^2$.\\
  Then the bending energy of g(x) is $\int_{-1}^{1}(g''(x))^2dx=8>6$

  (ii)Since $\int_{-1}^{1}(\cos(\frac{\pi}{2})x)^2dx=\frac{\pi^4}{16}>6$, hence the conclusion holds.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral5}}
\begin{solution}
  (a)By definition, we have $B_i^0(x)=\left\{
  \begin{aligned}
  &1\qquad x\in (t_i-1,t_i]\\
  &0\qquad otherwise
  \end{aligned}
  \right.$ and recursive definition$B_i^{n+1}(x)=\frac{x-t_{i-1}}{t_{i+n}-t_{i-1}}B_i^n(x)+\frac{t_{i+n+1}-x}{t_{i+n+1}-t_i}B_{i+1}^n(x)$

  Then$$B_i^1=\left\{
  \begin{aligned}
  &\frac{x-t_{i-1}}{t_{i}-t_{i-1}}\qquad x\in (t_{i-1},t_i]\\
  &\frac{t_{i+1}-x}{t_{i+1}-t_i}\qquad x\in (t_i,t_{i+1}]
  \end{aligned}
  \right.$$

  Hence
  $$B_{i+1}^1=\left\{
  \begin{aligned}
  &\frac{x-t_{i }}{t_{i+1}-t_{i }}\qquad x\in (t_{i },t_{i+1}]\\
  &\frac{t_{i+2}-x}{t_{i+2}-t_{i+1}}\qquad x\in (t_{i+1},t_{i+2}]
  \end{aligned}
  \right.$$

  Therefore, $$B_i^2(x)=\left\{\begin{array}{ll}
\frac{\left(x-t_{i-1}\right)^{2}}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i}-t_{i-1}\right)}, & x \in\left(t_{i-1}, t_{i}\right] ; \\
\frac{\left(x-t_{i-1}\right)\left(t_{i+1}-x\right)}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i+1}-t_{i}\right)}+\frac{\left(t_{i+2}-x\right)\left(x-t_{i}\right)}{\left(t_{i+2}-t_{i}\right)\left(t_{i+1}-t_{i}\right)}, & x \in\left(t_{i}, t_{i+1}\right] ; \\
\frac{\left(t_{i+2}-x\right)^{2}}{\left(t_{i+2}-t_{i}\right)\left(t_{i+2}-t_{i+1}\right)}, & x \in\left(t_{i+1}, t_{i+2}\right] ; \\
0, & \text { otherwise. }
\end{array}\right.$$

 (b)$$\frac{d}{dx}B_i^2(x)=\left\{\begin{array}{ll}
\frac{2\left(x-t_{i-1}\right)}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i}-t_{i-1}\right)}, & x \in\left(t_{i-1}, t_{i}\right] ; \\
\frac{\left(t_{i+1}+t_{i-1}-x\right)}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i+1}-t_{i}\right)}+\frac{\left(t_{i+2}+t_i-x\right)}{\left(t_{i+2}-t_{i}\right)\left(t_{i+1}-t_{i}\right)}, & x \in\left(t_{i}, t_{i+1}\right] ; \\
\frac{-2\left(t_{i+2}-x\right)}{\left(t_{i+2}-t_{i}\right)\left(t_{i+2}-t_{i+1}\right)}, & x \in\left(t_{i+1}, t_{i+2}\right] ; \\
0, & \text { otherwise. }
\end{array}\right.$$

Hence we have $$\lim _{x \rightarrow t_{i}^{-}} \frac{d}{d x} B_{i}^{2}(x)=\lim _{x \rightarrow t_{i}^{+}} \frac{d}{d x} B_{i}^{2}(x)=\frac{2}{t_{i+1}-t_{i-1}} , \lim _{x \rightarrow t_{i+1}^{-}} \frac{d}{d x} B_{i}^{2}(x)=\lim _{x \rightarrow t_{i+1}^{+}} \frac{d}{d x} B_{i}^{2}(x)=\frac{-2}{t_{i+2}-t_{i}}$$

Hence, $\frac{d}{dx}B^2_i(x)$ is continuous at $t_i$ and $t_{i+1}$

(c)Let $\frac{d}{dx}B_i^2(x)=0$, hence$$x^*=\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}.$$

(d)Consider extremum point $t_{i-1},x^*,t_{i+1}.$ Then $B_i^2(t_{i-1})=B_i^2(t_{i+2})=0$ and
$$B_i^2(x^*)= \frac{t_{i+2}-t_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}<1$$

Therefore $B_i^2(x)\in [0,1)$

(e)For example i=0. When $t_i=i$, we just need to translate the plot as x axis. The example plots are as follows.
\begin{figure}[H]
	\centering
	\includegraphics[width=5in]{figures/Bi2.png}
	\label{fig_sim}
\end{figure}
\begin{figure}[H]
	\centering
	\includegraphics[width=\linewidth]{figures/Bo2-2.png}
	\label{fig_sim}
\end{figure}

\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral6}}
\begin{solution}

$$LHS=\frac{\left(t_{i+2}-x\right)_{+}^{2}-\left(t_{i+1}-x\right)_{+}^{2}} {\left(t_{i+2}-t_{i+1}\right)\left(t_{i+2}-t_{i}\right)}- \frac{\left(t_{i+1}-x\right)_{+}^{2}-\left(t_{i}-x\right)_{+}^{2}}{\left(t_{i+1}-t_{i}\right) \left(t_{i+2}-t_{i}\right)}-\frac{\left(t_{i+1}-x\right)_{+}^{2}-\left(t_{i}-x\right)_{+}^{2}} {\left(t_{i+1}-t_{i}\right)\left(t_{i+1}-t_{i-1}\right)}+\frac{\left(t_{i}-x\right)_{+}^{2}- \left(t_{i-1}-x\right)_{+}^{2}}{\left(t_{i}-t_{i-1}\right)\left(t_{i+1}-t_{i-1}\right)}$$

When  $x<t_{i-1}$  or  $x>t_{i+2}$ , then $LHS  =  RHS  =0$ .

When  $x \in\left(t_{i-1}, t_{i}\right]$, then $LHS=\frac{\left(x-t_{i-1}\right)^{2}}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i}-t_{i-1}\right)}=RHS$

When  $x \in\left(t_{i-1}, t_{i}\right]$, then $LHS=\frac{\left(x-t_{i-1}\right)\left(t_{i+1}-x\right)}{\left(t_{i+1}-t_{i-1}\right)\left(t_{i+1}-t_{i}\right)}+\frac{\left(t_{i+2}-x\right)\left(x-t_{i}\right)}{\left(t_{i+2}-t_{i}\right)\left(t_{i+1}-t_{i}\right)}=  RHS$

When  $x \in \left(t_{i-1}, t_{i}\right]$, then $LHS=\frac{\left(t_{i+2}-x\right)^{2}}{\left(t_{i+2}-t_{i}\right)\left(t_{i+2}-t_{i+1}\right)}=RHS$.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral7}}
\begin{proof}

  Consider the integration $$\int_{t_{i-1}}^{t_{i+n}}\frac{d}{dx}B^n_i(x)$$
  Then by the derivatives of B-splines, we have
  $$\begin{aligned}
  \int_{t_{i-1}}^{t_{i+n}}\frac{d}{dx}B^n_i(x)&=
  \int_{t_{i-1}}^{t_{i+n}}\left(\frac{nB_i^{n-1}(x)}{t_{i+n-1}-t_{i-1}}
  -\frac{nB_{i+1}^{n-1}(x)}{t_{i+n}-t_i}\right)\\
  &=\frac{n\int_{t_{i-1}}^{t_{i+n}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
  -\frac{n\int_{t_{i-1}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_i}\\
  \end{aligned}$$
 That is
 $$B_{i}^{n}\left(t_{i+n+1}\right)-B_{i}^{n}\left(t_{i-1}\right)=\int_{t_{i-1}}^{t_{i+n-1}} \frac{n B_{i}^{n-1}}{t_{i+n-1}-t_{i-1}}-\int_{t_{i}}^{t_{i+n}} \frac{n B_{i+1}^{n-1}(x)}{t_{i+n}-t_{i}}=0$$

 Hence,
 $$\int_{t_{i-1}}^{t_{i+n-1}} \frac{n B_{i}^{n-1}}{t_{i+n-1}-t_{i-1}}=\int_{t_{i}}^{t_{i+n}} \frac{n B_{i+1}^{n-1}(x)}{t_{i+n}-t_{i}}=C$$

 Then the scaled integral of a B-spline $B^i_n(x)$ over its support is independent of its index i even if the spacing of the knots is not uniform.
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral8}}
\begin{solution}
  (a)
  \begin{table}[H]
    \centering
    \begin{tabular}{l|c c r}
      $x_i$ & $x_i^4$ &  &   \\
      $x_{i+1}$ & $x_{i+1}^4$ & $(x_{i+1}^4-x_{i+1}^4)/(x_{i+1}-x_i)$ &   \\
      $x_{i+2}$ & $x_{i+2}^4$ & $(x_{i+2}^4-(x_{i+1}^4-x_{i+1}^4)/(x_{i+1}-x_i))/(x_{i+2}-x_{i+1})$ & $\sum_{i\leq j \leq k\leq i+2}x_j x_k$ \\
    \end{tabular}
  \end{table}
  By the definition of $\tau _k(x_1, x_{2},\cdots ,x_{n})$, we have $\tau _2(x_i,x_{i+1}, x_{i+2})=[x_i,x_{i+1}, x_{i+2}]x^4$

(b) By Lemma 3.45, we have

$$\begin{aligned}
&\left(x_{n+1}-x_{1}\right) \tau_{k}\left(x_{1}, \ldots, x_{n}, x_{n+1}\right) \\
=& \tau_{k+1}\left(x_{1}, \ldots, x_{n}, x_{n+1}\right)-\tau_{k+1}\left(x_{1}, \ldots, x_{n}\right) \\
&-x_{1} \tau_{k}\left(x_{1}, \ldots, x_{n}, x_{n+1}\right) \\
=& \tau_{k+1}\left(x_{2}, \ldots, x_{n}, x_{n+1}\right)+x_{1} \tau_{k}\left(x_{1}, \ldots, x_{n}, x_{n+1}\right) \\
&-\tau_{k+1}\left(x_{1}, \ldots, x_{n}\right)-x_{1} \tau_{k}\left(x_{1}, \ldots, x_{n}, x_{n+1}\right) \\
=& \tau_{k+1}\left(x_{2}, \ldots, x_{n}, x_{n+1}\right)-\tau_{k+1}\left(x_{1}, \ldots, x_{n}\right) .
\end{aligned}$$

The rest of the proof is an induction on  n . For  n=0 , that is

$\tau_{m}\left(x_{i}\right)=\left[x_{i}\right] x^{m}$,

which is trivially true. Now suppose the conclusion holds for a nonnegative integer  n<m . Then the induction hypothesis yields

$$\begin{aligned}
& \tau_{m-n-1}\left(x_{i}, \ldots, x_{i+n+1}\right) \\
=& \frac{\tau_{m-n}\left(x_{i+1}, \ldots, x_{i+n+1}\right)-\tau_{m-n}\left(x_{i}, \ldots, x_{i+n}\right)}{x_{i+n+1}-x_{i}} \\
=& \frac{\left[x_{i+1}, \ldots, x_{i+n+1}\right] x^{m}-\left[x_{i}, \ldots, x_{i+n}\right] x^{m}}{x_{i+n+1}-x_{i}} \\
=& {\left[x_{i}, \ldots, x_{i+n+1}\right] x^{m} }
\end{aligned}$$

which completes the proof.
\end{solution}
\end{document}
